package selfLearn.theList.symbol;

/**
 * 描述:有序符号表
 * 刚才实现的符号表，我们可以称之为无序符号表，因为在插入的时候，并没有考虑键值对的顺序，而在实际生活中，
 * 有时候我们需要根据键的大小进行排序，插入数据时要考虑顺序，那么接下来我们就实现一下有序符号表。
 *
 * @return:
 * @author: chenwei
 * @date : 2022/2/16 14:12:57
 */
public class OrderSymbolTable<Key extends Comparable<Key>, Value> {
    private Node head;
    private Integer n;

    private class Node {
        private Key key;
        private Value value;
        private Node next;

        public Node(Key key, Value value, Node node) {
            this.key = key;
            this.value = value;
            this.next = node;
        }

    }

    public OrderSymbolTable() {
        this.head = new Node(null, null, null);
        this.n = 0;
    }

    //往符号表中插入键值对
    public void put(Key key,Value value){
        //定义两个Node变量，分别记录当前结点和当前结点的上一个结点

        Node curr = head.next;
        Node pre = head;

        while(curr!=null &&key.compareTo(curr.key)>0){

            //变换当前结点和前一个结点即可
            pre = curr;
            curr = curr.next;
        }

        //如果当前结点curr的键和要插入的key一样，则替换
        if (curr!=null && key.compareTo(curr.key)==0){
            curr.value = value;
            return;
        }

        //如果当前结点curr的键和要插入的key不一样，把新的结点插入到curr之前
        Node newNode = new Node(key, value, curr);
        pre.next = newNode;

        //元素的个数+1；
        n++;

    }


    //遍历符号表
    public void foreachTable() {
        if (head.next == null) {
            return;
        }
        Node tar = head;
        while (tar.next != null) {
            tar = tar.next;
            System.out.println("key=" + tar.key + ",value=" + tar.value);
        }
    }
}
